package com.zx._12_算法.algorithm.sort.demo;

import com.zx._12_算法.Nums;

// 由大到小
// 2020/04/09   35 分钟
// 2020/04/18   31 分钟
// 2020/04/25   21 分钟
// 2020/05/18   27 分钟
// 2020/06/19   41 分钟
public class Demo2 {

    // 冒泡
    public static void main1(String[] args) {
        int[] nums = Nums.nums;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j + 1] > nums[j]) {
                    swap(nums, j, j + 1);
                }
            }
        }
        Nums.print();
    }

    // 选择排序，简单排序
    public static void main2(String[] args) {
        int[] nums = Nums.nums;
        for (int i = 0; i < nums.length; i++) {
            int idx = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[idx] < nums[j]) {
                    idx = j;
                }
            }
            swap(nums, i, idx);
        }
        Nums.print();
    }

    // 插入排序
    public static void main3(String[] args) {
        int[] nums = Nums.nums;
        for (int i = 1; i < nums.length; i++) {
            int n = nums[i];
            int idx = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < n) {
                    nums[j + 1] = nums[j];
                } else {
                    idx = j + 1;
                    break;
                }
            }
            nums[idx] = n;
        }
        Nums.print();
    }

    // 希尔排序
    public static void main4(String[] args) {
        int[] nums = Nums.nums;
        int len = nums.length;
        int gap = len / 2;
        while (gap != 0) {
            for (int i = gap; i < nums.length; i = i + gap) {
                int n = nums[i];
                int idx = i - gap;

                for (int j = i - gap; j >= 0; j = j - gap) {
                    if (nums[j] < n) {
                        nums[j + gap] = nums[j];
                    } else {
                        idx = j + gap;
                        break;
                    }
                }

                nums[idx] = n;
            }
            gap = gap / 2;
        }
        Nums.print();
    }

    // 快速排序
    public static void main5(String[] args) {
        int[] nums = Nums.nums;
        fun1(nums, 0, nums.length - 1);
        Nums.print();
    }

    public static void fun1(int[] arr, int begin, int end) {
        int left = begin;
        int right = end;

        while (left < right) {
            int base = arr[left];

            while (left < right && arr[right] <= base) {
                right--;
            }
            if (arr[right] >= base) {
                swap(arr, right, left);
            }

            while (left < right && arr[left] >= base) {
                left++;
            }
            if (arr[left] <= base) {
                swap(arr, right, left);
            }

        }

        if (begin < left) {
            fun1(arr, begin, left - 1);
        }

        if (right < end) {
            fun1(arr, right + 1, end);
        }

    }


    // 堆排序
    public static void main(String[] args) {
        int[] nums = Nums.nums;
        int len = nums.length;
        // 1. 构建最小堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            fun2(nums, i, len);
        }
        // 2. 交换位置，并调整最小堆
        for (int i = len - 1; i > 0; i--) {
            swap(nums, 0, i);
            fun2(nums, 0, i);

        }
        Nums.print();
    }


    public static void fun2(int[] arr, int heap, int len) {
        int mix = arr[heap];
        for (int k = 2 * heap + 1;
                k < len;
                k = 2 * k + 1) {

            if (k + 1 < len && arr[k + 1] < arr[k]) {
                k++;
            }

            if (arr[k] < mix) {
                swap(arr, heap, k);
                heap = k;
            } else {
                break;
            }
        }
    }


    private static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

}
